package week7.Chapter9_排序与查找.seatwork;

import java.util.Scanner;

/**
 * 把自己的学号加21，例如学号为1，把22添加到序列后面，使用链地址法，解决冲突。
 编程实现，并测试。
 要求计算asl，输出冲突次数。
 @author 唐才铭
 @time2018-10-21 from 18：35 to 23:12
 */
public class Hash_Collisions {
    public static int Number_of_conflict = 0;  // 冲突次数

    //  相关节点类
    public static class Node{
        int key;  //  关键字
        Node next;

        public int getKey() {
            return key;
        }

    }
    public static Node[] hashtable ;

    //  对所有已知元素进行查找
    public static boolean HashSearchall(int[] data){
        int key = 0;
        boolean found = true;
        int search_length = 0; // 总查找长度
        // 遍历查找哈希表中的所有元素
        for (int i = 0 ; i < data.length;i++) {
            int success_search_length = 1; //  单个节点成功查找长度

            hashtable = createHashTable1(data);

            // 查找key是否在哈希表中
            key = data[i];
            int k = key % 11;
            Node currrent = hashtable[k];

            //  如果当前头结点不符合则移动至下一节点
            while (currrent != null && currrent.key != key) {

                success_search_length++;
                currrent = currrent.next;

            }

            if (currrent == null) {
                found =  false;
            } else {
                found =  true;
            }

            System.out.println("查找元素：" + key + "的结果为：  " + found);
            search_length+=success_search_length;

        }
        System.out.println("ASL = " +  search_length + "/" + data.length);
        return found;
    }

    //  对哈希表中的单个元素进行查找
    public static boolean HashSearch(int[] data,int key){
        int sucess_search_length = 1;  //  单个节点成功查找长度
        boolean found = true;
        hashtable = createHashTable1(data);
        // 查找key是否在哈希表中
        int k = key % 11;
        Node currrent = hashtable[k];
        while (currrent != null && currrent.key != key) {
            sucess_search_length++;
            currrent = currrent.next;

        }
        if (currrent == null) {
            found= false;
        } else {
            found= true;
        }
        if (found==true) {
            System.out.println("The success search length is:  " + sucess_search_length + "/" + data.length);
        }
        return found;
    }

    //  用所给数组建立哈希表
    public static Node[] createHashTable1(int[] data) {
        Node[] hashtable = new Node[11];
        int k;        //哈希函数计算的单元地址
        for (int i = 0; i < data.length; i++) {
            Node node = new Node();
            node.key = data[i];
            k = data[i] % 11;

            // 如果当前符合位置的头结点为空，则当前值即为符合位置的头结点
            if (hashtable[k] == null) {
                hashtable[k] = node;

            }
            else
                {
                //  不然接在当前位置的头结点后方
                Number_of_conflict++;
                Node current = hashtable[k];
                while(current.next != null) {
                    current = current.next;
                }
                current.next = node;
            }
        }
        return hashtable;
    }

    // 用所给数组建立哈希表并打印
    public static void createHashTable(int[] data) {
        Node[] hashtable = new Node[11];
        int k;
        for (int i = 0; i < data.length; i++) {
            Node node = new Node();
            node.key = data[i];
            k = data[i] % 11;

            if (hashtable[k]==null) {
                hashtable[k] = node;
            }else {
                Node current = hashtable[k];
                while(current.next != null) {
                    current = current.next;
                }
                current.next = node;
            }
        }

        //输出hash表中的元素
        String result = ""; // 保存哈希表所有头结点及其后方节点值
        String temp = "";  //  保留单个头结点及其后方节点值

        //  遍历所有头结点
        for (int i = 0 ; i < hashtable.length;i++){
            Node node = hashtable[i];
            temp = " ";

            // 对空节点不做处理
            if (hashtable[i]!=null){
                int size = 0;  //  记录当前位置的链表长度
                Node temp_node = hashtable[i];
                while (temp_node!=null){
                    size++;
                    temp_node = temp_node.next;
                }

                // 打印当前位置的链表元素
                for (int j = 0 ; j < size; j++){
                    temp += node.getKey() + " ";
                    node = node.next;
                    if (node==null){
                        break;
                    }
                }
                result += temp + "\n" ;
            }
        }
        System.out.println(result);
    }
    public static void main(String[] args) {
        int[] data = {11,78,10,1,3,2,4,21};
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter your student number:  ");
        int student_number = scanner.nextInt();

        int[] new_data = new int[data.length + 1];
        new_data[new_data.length - 1] = student_number + 21;
        for (int i = 0; i < data.length; i++) {
            new_data[i] = data[i];
        }
        System.out.print("Keywords sequence elements:  ");
        for (int i = 0; i < new_data.length; i++) {
            System.out.print(new_data[i]+" ");
        }
        System.out.println();
        //  打印哈希表
        System.out.println("Elements in the hash table (print only the portion of existing elements) :  ");
        Hash_Collisions1.createHashTable(new_data);

        //  打印冲突次数
        System.out.println("The number of conflicts is:  ");
        Hash_Collisions1.createHashTable1(new_data);
        System.out.println(Hash_Collisions1.Number_of_conflict);
        System.out.println("选择查找方式：1 看着就行；其他数字 自己输入");
        int choose = scanner.nextInt();
        if (choose==1){
            System.out.println(Hash_Collisions1.HashSearchall(new_data));
        }
        else
        {
            System.out.println("Enter an element you want to find:  ");
            int input = scanner.nextInt();
            System.out.println("The result of the element " +input+ " in the lookup table " +
                    "is :  " +   Hash_Collisions1.HashSearch(new_data,input) );
        }
    }
}
